package pl.wroc.uni.ii.pastuszka.algorithms.evolutionary.genetic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;

import pl.wroc.uni.ii.pastuszka.algorithms.evolutionary.Individual;
import pl.wroc.uni.ii.pastuszka.algorithms.evolutionary.utils.BinaryRandom;

public class SGA extends GeneticAlgorithmSchema {

  private float crossoverProbability;
  private float mutationProbability;

  private Random rand = new Random();

  private ArrayList<Individual> newGeneration;

  public void setCrossoverProbability(float crossoverProbability) {
    this.crossoverProbability = crossoverProbability;
  }

  public void setMutationProbability(float mutationProbability) {
    this.mutationProbability = mutationProbability;
  }

  public SGA(int chromosomeLength, int populationSize, float crossoverProbability, float mutationProbability) {
    super(chromosomeLength, populationSize);
    setCrossoverProbability(crossoverProbability);
    setMutationProbability(mutationProbability);
  }

  private void chooseParents() {
    newGeneration = new ArrayList<Individual>(populationSize);

    float[] prefixSums = computeRankPrefixSums();
    for (int i = 0; i < populationSize; ++i) {
      int searchResult = getRandomUsingRouletteMethod(prefixSums);
      newGeneration.add(new Individual(population.get(searchResult)));
    }
  }

  private int getRandomUsingRouletteMethod(float[] prefixSums) {
    float totalSum = prefixSums[populationSize - 1];
    float keyToFind = rand.nextFloat() * totalSum;
    int searchResult = Arrays.binarySearch(prefixSums, keyToFind);
    if (searchResult < 0) {
      searchResult = -searchResult - 1;
    }
    return searchResult;
  }

  private float[] computeRankPrefixSums() {
    Collections.sort(population, Individual.RANK_COMPARATOR);
    float worstRank = population.get(0).rank;
    float[] prefixSums = new float[populationSize];

    prefixSums[0] = 0;
    for (int i = 1; i < populationSize; ++i) {
      prefixSums[i] = prefixSums[i - 1] + population.get(i).rank - worstRank;
    }
    return prefixSums;
  }

  private void breed() {
    for (int i = 0; i < populationSize / 2; ++i) {
      if (BinaryRandom.getBoolean(crossoverProbability)) {
        Individual mother = newGeneration.get(2 * i);
        Individual father = newGeneration.get(2 * i + 1);
        crossoverGenes(mother, father);
      }
    }
  }

  private void crossoverGenes(Individual mother, Individual father) {
    int cutPoint = rand.nextInt(chromosomeLength);
    for (int i = cutPoint; i < chromosomeLength; ++i) {
      swapGene(mother, father, i);
    }
  }

  private void swapGene(Individual mother, Individual father, int j) {
    int fatherGene = father.chromosome[j];
    father.chromosome[j] = mother.chromosome[j];
    mother.chromosome[j] = fatherGene;
  }

  protected void replaceOldPopulation() {
    evaluatePopulation(newGeneration);
    Collections.sort(newGeneration, Individual.RANK_COMPARATOR);
    ArrayList<Individual> oldPopulation = population;

    population = new ArrayList<Individual>(populationSize);
    int i = populationSize - 1, j = populationSize - 1;
    for (int k = 0; k < populationSize; ++k) {
      if (newGeneration.get(i).rank > oldPopulation.get(j).rank) {
        population.add(new Individual(newGeneration.get(i--)));
      }
      else {
        population.add(new Individual(oldPopulation.get(j--)));
      }
    }
  }

  private void mutate() {
    for (int i = 0; i < populationSize; ++i) {
      Individual current = newGeneration.get(i);
      for (int j = 0; j < chromosomeLength; ++j) {
        if (BinaryRandom.getBoolean(mutationProbability)) {
          current.chromosome[j] = 1 - current.chromosome[j];
        }
      }
    }
  }

  @Override
  protected void applyGeneticOperators() {
    chooseParents();
    breed();
    mutate();
    replaceOldPopulation();
  }

  @Override
  protected void finishIteration() {
  }
}
